package LeetcodeTest_thirty;
//543.二叉树的直径

import java.util.Scanner;

public class diameterOfBinaryTree
{
    public static void main(String[] args)
    {
        TreeNode root=null;
        root=Solution.createTree(root);
        System.out.println(Solution.diameterOfBinaryTree(root));
    }
}
class Solution
{
    public static int maxDepth=0;
    public static int diameterOfBinaryTree(TreeNode root)
    {
        difs1(root,0,0);
        int answer=maxDepth;
        maxDepth=0;
        return answer;
    }
    public static int difs1(TreeNode root,int left,int right)
    {
        if(root!=null)
        {
            left=1+difs1(root.left,left,right);
            right=1+difs1(root.right,left,right);
            maxDepth=Math.max(maxDepth,left+right-2);
            return Math.max(left,right);
        }
        else
            return 0;
    }
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
}
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}